package com.wdc.queue;

@SuppressWarnings("all")



 //实现小顶堆
 public class MinHeap {



     ListNode[] array;
     int size;
     public MinHeap(int capacity) {
         array = new ListNode[capacity];

     }

     /*
     1. 将元素添加到数组尾部
     2. 元素上浮与父节点比较
     3. 直到找到合适位置或者到了堆顶
      */

     public boolean offer(ListNode offered) {

         if (isFull()) {
             return false;
         }
         int child = size++;
         int parent = (child - 1) / 2;
         while(offered.val < array[parent].val && child >= 0){
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;

         }

         array[child] = offered;
         return true;



     }
     private void swap(int i, int j) {
         ListNode temp = array[i];
         array[i] = array[j];
         array[j] = temp;
     }

     /*
     1. 取出堆顶元素
     2. 将尾部元素放到堆顶
     3. 元素下沉与子节点比较
     直到找到合适位置或者到了堆底
      */
     public ListNode poll() {
         if (isEmpty()) {
             return null;
         }
         swap(0,size-1);
         size--;
         ListNode e = array[size];
         array[size] = null;  //help GC

         //下潜

         return  e;

     }


     /*
     1. 没有子孩子时，直接返回
     2. 与子孩子中较小者交换
      */
     private void down(int parent) {
         //找出两个子孩子
         int left = parent * 2 + 1;
         int rignt = left + 1;
         int min = parent;
         if (array[min].val > array[left].val && left < size){
             min = left;
         }
         if (array[min].val > array[rignt].val && left < size){
             min = rignt;
         }
         if (min!= parent){
             swap(parent,min);
             down(min);
         }


     }




     public boolean isEmpty() {
         return size == 0;
     }

     public boolean isFull() {
         return size == array.length;
     }



}


